#pragma once
#include <iostream>

template<class T>
struct Node
{
public:
    Node(const T& key = 0)
    :_key(key), _left(nullptr), _right(nullptr)
    {}
public:
    T _key;
    Node<T>* _left;
    Node<T>* _right;
};

//二叉搜索树
template<class T>
class BSTree
{
public:
	//构造函数
	BSTree()
    :_root(nullptr)
    {}

	//拷贝构造函数
	BSTree(const BSTree<T>& t)
    {
        _root = _Copy(t._root);
    }

	//赋值运算符重载函数
	BSTree<T>& operator=(const BSTree<T> t)
    {
        _swap(_root, t._root);
        return *this;
    }

	//析构函数
	~BSTree()
    {
        _Destory(_root);
        _root = nullptr;
    }

	//插入函数
	bool Insert(const T& key)
    {
        return _Insert(_root, key);
    }

	//删除函数
	bool Erase(const T& key)
    {
        return _Erase(_root, key);
    }

	//查找函数
	Node<T>* Find(const T& key)
    {
        return _Find(_root, key);
    }

	//中序遍历
	void InOrder()
    {
        _InOrder(_root);
        std::cout << std::endl;
    }

private:
    Node<T>* _Copy(const Node<T>* root)
    {
        if(root == nullptr) return nullptr;
        Node<T>* newnode = new Node<T>(root->_key);
        newnode->_left = _Copy(root->_left);
        newnode->_right = _Copy(root->_right);
        return newnode;
    }

    void _swap(Node<T>* t1, Node<T>* t2)
    {
        Node<T>* tmp = t1;
        t1 = t2;
        t2 = tmp;
    }

    void _Destory(Node<T>* root)
    {
        if(root == nullptr) return;
        _Destory(root->_left);
        _Destory(root->_right);
        delete root;
    }

    bool _Insert(Node<T>*& root, const T& key)
    {
        if(root == nullptr)
        {
            root = new Node<T>(key);
            return true;
        }
        else
        {
            if(key < root->_key)
            {
                _Insert(root->_left, key);
            }
            else if(key > root->_key)
            {
                _Insert(root->_right, key);
            }
            else
            {
                return false;
            }
            return true;
        }
    }

    bool _Erase(Node<T>*& root, const T& key)
    {
        if(root == nullptr) return false;
        if(key < root->_key) return _Erase(root->_left, key);
        else if(key > root->_key) return _Erase(root->_right, key);
        else // ==
        {
            if(root->_left && root->_right)
            {
                // 找右子树最小的或左子树最大的节点替换
                Node<T>* right_min_parent = root;
                Node<T>* right_min = root->_right;
                while(right_min->_left)
                {
                    right_min_parent = right_min;
                    right_min = right_min->_left;
                }
                root->_key = right_min->_key;
                if(right_min == right_min_parent->_left)
                {
                    right_min_parent->_left = right_min->_right;
                }
                else
                {
                    right_min_parent->_right = right_min->_right;
                }
                delete right_min;
            }
            else if(root->_left == nullptr)
            {
                Node<T>* tmp = root;
                root = root->_right;
                delete tmp;
            }
            else
            {
                Node<T>* tmp = root;
                root = root->_left;
                delete tmp;
            }
        }
        return true;
    }

    Node<T>* _Find(Node<T>* root, const T& key)
    {
        if(root == nullptr) return nullptr;
        if(root->_key == key) return root;
        else if(key < root->_key) return _Find(root->_left, key);
        else return _Find(root->_right, key);
    }

    void _InOrder(Node<T>* root) // 中序遍历
    {
        if(root == nullptr) return;
        _InOrder(root->_left);
        std::cout << root->_key << ' ';
        _InOrder(root->_right);
    }

private:
	Node<T>* _root; //指向二叉搜索树的根结点
};
